1. Field of the Invention
This invention relates to page-oriented output devices, and more particularly to a method and apparatus for efficiently rendering and printing bands of image information defined by a page description language.
2. Description of Related Art
Page-oriented output devices, such as laser printers, commonly receive data in page description language form before starting the printing process. With a page description language (PDL), a page is represented using graphics, text, and images that can be specified to be located anywhere on the page, and in any order, using successive commands of the language. The PDL commands reflect the way the page is composed. However, before printing, the received data must be rasterized so the page print mechanism ("print engine") in the printer can print the page while moving the print media (e.g, paper) uniformly in one direction, usually top to bottom.
Rasterization is the process of converting data that represent a page or portion of a page into a series of individual dots or pixels across the printed page to form a raster scanline, producing successive scanlines one after another down the page. The complete set of scanlines for a page is the raster data for the page. Rasterization is performed in the page printer by a raster generator.
Many page printers rasterize and store the entire raster data for a page before starting to send data to the print engine of the printer. The print engine runs at a predetermined speed. Therefore, precomputing the entire page of raster data ensures that each raster scanline is ready to send when needed by the print engine.
To store the raster data for an entire page may require substantial memory. Laser printers commonly have about 80 square inches of graphic information printed on a page at a resolution of 300 dots per inch, both horizontally and vertically. With one bit indicating each dot to be printed or left unprinted, over 875K bytes are required to store the raster data for an entire page. To increase the printer speed, a second page of raster data may be computed and stored in additional memory as the raster data for the first page is being sent incrementally to the print engine. Having a second page doubles the memory requirements.
New printer technology is enabling 600.times.600 dot (or pixel) resolution continuous tone color printing, which may require 24 bits per pixel or more. If full-page storage is used to meet high resolution color requirements, over 80 million bytes of memory per page are required; 160 million bytes of memory are thus required for storing two pages. This is expensive, even relative to the cost of a high-performance color printer. The memory requirements become even worse for higher resolution printers.
For low-end printers, the memory requirements are less, but the portion of the cost of the memory relative to other printer costs is higher. To provide users with improved printers at lower cost, memory requirements must be reduced.
Several methods have been employed to reduce printer memory requirements while minimizing "printer overrun" errors. A printer overrun error occurs when rasterization does not keep up with the predetermined speed of the print engine. A printer overrun prevents printing the remainder of the page. One method, taught by Cuzzo, et al., in U.S. Pat. No. 5,129,049, is to store the second page in a format that is more compact than a raster image, so the memory required for it is less than that required for the first full page raster image. The second page could be stored in its original PDL command representation, but doing so would not yield the advantage of overlapping the processing time for rasterizing the second page while the first page is being printed. Instead, the PDL commands for the second page are converted on input to an intermediate representation called a "display list." A display list is a sequence of display list commands. Display list commands are relatively simple drawings commands that are faster to rasterize than the original PDL commands. However, the display list page representation is more compact than a full page of raster data.
Display list commands for the page can be sorted by their position on the page as they are created. By sorting, the display list commands for a page can be separated into multiple sublists. Each sublist is localized for a particular area of the page. This results in display list commands being localized for each area, which leads to another method of saving memory described below.
Rather than rasterize the entire display list for a page before printing, the page is divided into horizontal strips or bands, and only some of the bands are rasterized before the start of the printing process. All the information for a particular band is contained in the display list commands for that band. Subsequent bands are rasterized after printing has started but before they are required by the print engine. By measuring or estimating the rasterization times and keeping track of the running total, some bands may be allowed to take longer to rasterize than others of the same size, so long as the cumulative time stays ahead of the print engine. This is described in the Cuzzo, et al patent referenced above and incorporated herein by reference. If the rasterization time for rasterization-on-the fly is too large, then one or more bands may be completely pre-rasterized. This approach helps ensure that the printing process will not fail due to running out of rasterization time, avoiding printer overruns.
For example, referring to FIG. 1, a page printer receives PDL commands 2 and converts the PDL command to display list commands 4. The display list commands 4 are stored in band representations that correspond to bands 8-1 through 8-10 on the printed page. If display list storage capacity becomes a limiting factor, display list commands 4 are converted to raster data or compressed raster data in band representations 6-1 through 6-10. Collectively, the band representations 6-1 through 6-10 form an intermediate page representation 10 of the data describing a printed page 12. The page 12 is printed by sequentially converting the various band representations 6-1 through 6-10 to raster data. Raster data for a raster scanline or band temporarily may be stored in a raster buffer 14 before printing.
The page data is received from a host computer as a sequence of PDL commands 2. The PDL commands 2 may include a combination of text and graphics commands as well as embedded imagery. Any individual PDL command may place text, graphics, or imagery on any part of the page, so that printing cannot begin until all of the PDL commands 2 for an entire page have been received and processed.
In the illustrated example, the page is logically divided into ten lateral bands 8-1 through 8-10. Each band has predefined upper and lower boundaries across the page. The bands typically are of equal size (but need not be). Each PDL command is translated, as it is received, into a series of display list commands 4. The display list commands 4 are generated so that each such command pertains only to a single band. Thus, if the print contribution from a PDL command 2 extends vertically over the whole page, it will result in at least one display list command 4 being generated in correspondence with each page band 8-1 through 8-10. If memory becomes a limitation, display list commands 4 for a band may be converted to another type of data representing the band, but if memory is not a limiting factor, all the presentations 6-1 through 6-10 will be in the form of display list commands 4 upon completion of the input of PDL commands 2.
Ultimately, the print engine requires a raster data representation for each band which may be stored in the raster buffer 14. In the raster data representation, the page 12 is described as a matrix of numbers, each number corresponding to a single pixel or dot to be printed on the page. The number value gives the color or intensity to be printed at that point.
While avoiding printer overruns and minimizing average memory requirement, such prior art methods still are subject to running out of memory for difficult cases. Accordingly, in co-pending patent application Ser. No. 08/021,190 entitled "Method and Apparatus for Saving Printer Memory" and assigned to the assignee of the present invention (herein incorporated by reference), an improved method is taught for overcoming such problems. In that method, data is supplied to the printer as a series of PDL commands. The PDL commands are converted by the raster generator upon input to an intermediate display list of drawing primitives that are then divided and sorted into commands associated with a plurality of bands. Depending upon the memory demands of the data for a particular page, the raster generator will keep each band in its display list representation or convert it into one of several other intermediate representations.
If, during input, the display list representation of the data fills the memory allotted to its storage, one or more of the bands is converted from display list format to raster format and compressed using a lossless compression algorithm. If storage of compressed bands subsequently exceeds available memory, raster data is further compressed using a lossy compression algorithm which can be assured to produce data sets that will fit within the memory allotment. Then additional display list commands are rasterized by decompressing the compressed bands, processing the new display list commands and recompressing the data using lossless or lossy compression as required. The time to rasterize each band can be estimated by the processor and stored, or the processor may actually compute and store the time for each band. Should memory for the compressed bands overflow at any point in the process, then the rasterizing times for the remaining bands may be determined or estimated and then stored without storing the raster output. Based on the stored rasterizing times, the processor determines for each band whether to rasterize it to the print engine on the fly, to pre-compute and store it as a lossless compressed raster data, to revert to a lossy-compressed pre-computed version, or to store it as uncompressed raster data.
However, while solving many of the problems of the prior art, the method described in the co-pending patent application requires greater computational complexity. The need to conditionally pre-render, compress, and/or decompress PDL print information means that computational resources are consumed that could have been used in simply rendering the PDL print information.
Thus, the present invention recognizes that it would be desirable to have a simpler method of controlling the printing of complex PDL pages that eliminates or reduces the need to pre-render, compress, and/or decompress PDL print information.